#pragma once
#include"BinarySearchList.h"

/*
* 二分查找
* 1. 对线性表进行分半, 产生 start, mid, end 三个索引
* 
* ** 当 start < end 时
* 2. 当 mid 的数据 大于 查找元素时, 查询范围变为 右半部分 start = mid + 1, end = end, mid = (start + end) / 2
* 3. 当 mid 的数据 小于 查找元素时, 查询范围变为 左半部分 start = start, end = mid - 1, mid = (start + end) / 2
* 4. 当 mid 的数据 等于 查找元素时, 则索引为 mid
* 
* ** 当 start == end 时
* 判断 start 的数据 是否等于 查询元素, 若等于, 则索引为 start, 否则数据不存在
*/
int BinartSearch(List* list, int data) {
	int start = 0;
	int end = list->num;
	int mid;

	int* listData = list->data;
	while (start < end) {
		mid = (start + end) / 2;

		if (listData[mid] > data) {
			end = mid - 1;
		}
		else if (listData[mid] < data) {
			start = mid + 1;
		}
		else {
			return mid;
		}
	}

	if (listData[start] == data)
		return start;

	else
		return -1;
}

int BinarySearchRecursion(List* list, int start, int end, int data) {
	if (start == end) {
		if (list->data[start] == data)
			return start;

		else
			return -1;
	}

	int mid = (start + end) / 2;
	if (list->data[mid] > data) {
		int t_end = mid - 1;
		BinarySearchRecursion(list, start, t_end, data);
	}
	else if (list->data[mid] < data) {
		int t_start = mid + 1;
		BinarySearchRecursion(list, t_start, end, data);
	}
	else {
		return mid;
	}
}